package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC90 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        Set<String> dict = new HashSet<>();


        public List<List<Integer>> subsetsWithDup(int[] arr) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(arr);
            List<Integer> curList = new LinkedList<>();
            subsetsWithDupRecur(arr, 0, res, curList);
            return res;
        }

        public void subsetsWithDupRecur(int[] arr, int start, List<List<Integer>> res,
                                        List<Integer> curList) {
            if (start == arr.length) {
                String serial = getSerial(curList);
                if (dict.contains(serial)) return;
                dict.add(serial);
                res.add(getCopyList(curList));
                return;
            }

            // not choose start
            subsetsWithDupRecur(arr, start + 1, res, curList);

            // choose
            curList.add(arr[start]);
            subsetsWithDupRecur(arr, start + 1, res, curList);
            curList.remove(curList.size() - 1);
        }

        public String getSerial(List<Integer> curList) {
            StringBuilder sb = new StringBuilder();
            for (Integer el : curList) {
                sb.append(el);
            }
            return sb.toString();
        }

        public List<Integer> getCopyList(List<Integer> curList) {
            List<Integer> copyList = new ArrayList<>();
            for (Integer el : curList) {
                copyList.add(el);
            }
            return copyList;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,2]");
        System.out.println(solution.subsetsWithDup(arr));
    }

    public static void main(String[] args) throws Exception {
        LC90 an = new LC90();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
